Crack redirection with thermal secondary loading

In the current paper crack redirection due to a strategic placing of a heat source in the vicinity of a crack tip is studied. Analysis suggests that for PMMA and considered temperature range the only factor responsible for the deviation of crack trajectory is thermal stress. The simulation of crack growth in PMMA under external tension and secondary heat loading shows that a moving heat source in the vicinity of a crack tip can serve as a pointer for the crack trajectory. In highly conductive materials, redirection can be possibly effected with low-power thermal dipoles.     

Local and global deadlock-detection in component-based systems are NP-hard

Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. We present here a polynomial time reduction from 3-SAT to the question whether an interaction system contains deadlocks.     

Optimal implementations of UPGMA and other common clustering algorithms

In this work we consider hierarchical clustering algorithms, such as UPGMA, which follow the closest-pair joining scheme. We survey optimal O(n²)-time implementations of such algorithms which use a ‘locally closest’ joining scheme, and specify conditions under which this relaxed joining scheme is equivalent to the original one (i.e. ‘globally closest’).     

Note on covering monotone orthogonal polygons with star-shaped polygons

In 1986, Keil provided an O(n²) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63]. In this paper we simplify the latter algorithm—we show that with a little modification, the first step Sweep1 of the discussed algorithm—which computes the top ceilings of horizontal grid segments—can be omitted.In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses O(k) additional space, where k is the size of the optimal solution—the algorithm in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63] uses both O(n) time and O(n) additional space.     

A Generic Pigment Model for Digital Painting

We propose a generic pigment model suitable for digital painting in a wide range of genres including traditional Chinese painting and water-based painting. The model embodies a simulation of the pigment-water solution and its interaction with the brush and the paper at the level of pigment particles; such a level of detail is needed for achieving highly intricate effects by the artist. The simulation covers pigment diffusion and sorption processes at the paper surface, and aspects of pigment particle deposition on the paper. We follow rules and formulations from quantitative studies of adsorption and diffusion processes in surface chemistry and the textile industry. The result is a pigment model that spans a continuum from the very wet to the very dry brush stroke effects. We also propose a new pigment mixing method based on machine learning techniques to emulate pigment mixing in real life as well as to support the creation of new artificial pigments. To experiment with the proposed model, we embedded the model in a sophisticated digital brush system. The combined system exhibits interactive speed on a modest PC platform. http://www.cs.hku.hk/~songhua/pigment provides supplementary materials for this paper.     

Smaller superconcentrators of density 28

An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. Here it is proved that such superconcentrators exist (by a random construction of certain expander graphs as building blocks) having density 28 (where the density is the number of edges divided by N). The best known density before this paper was 34.2 [U. Schöning, Construction of expanders and superconcentrators using Kolmogorov complexity, J. Random Structures Algorithms 17 (2000) 64-77] or 33 [L.A. Bassalygo, Personal communication, 2004].     

Determining the Castability of Simple Polyhedra

A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be removed from the object without breaking the cast part or the object. If we assume that the cast parts are each removed by a single translation, it is shown that for a simple polyhedron with n vertices, castability can be decided in time and linear space using a simple algorithm. A more complicated algorithm solves the problem in time and space, for any fixed ε > 0. In the case where the cast parts are to be removed in opposite directions, a simple O(n ² )-time algorithm is presented. Finally, if the object is a convex polyhedron and the cast parts are to be removed in opposite directions, a simple algorithm is presented. Received June 1, 1994; revised May 25, 1995.     

Parallelism in ILU-preconditioned GMRES

A parallel implementation of the preconditioned GMRES method is described. The method is used to solve the discretized incompressible Navier–Stokes equations. A parallel implementation of the inner product is given, which appears to be scalable on a massively parallel computer. The most difficult part to parallelize is the ILU-preconditioner. We parallelize the preconditioner using ideas proposed by Bastian and Horton (P. Bastian, G. Horton, SIAM. J. Stat. Comput. 12 (1991) 1457–1470). Contrary to some other parallel methods, the required number of iterations is independent of the number of processors used. A model is presented to predict the efficiency of the method. Experiments are done on the Cray T3D, computing the solution of a two-dimensional incompressible flow. Predictions of computing time show good correspondence with measurements.     

An optimal algorithm for the boundary of a cell in a union of rays

In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal (n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.This work was partly supported by CEE ESPRIT Project P-940, by the Ecole Normale Supérieure, Paris, and by NSF Grant ECS-84-10902.This work was done in part while this author was visiting the Ecole Normale Supérieure, Paris, France.